from typing import Hashable, Iterator, List, Tuple, Union

import networkx

GridLocation = Tuple[int, int]
Graph = Union["BaseGraph", networkx.Graph]


class BaseGraph:
    def __init__(self) -> None:
        pass

    def neighbors(self, node: Hashable) -> List[Hashable]:
        raise NotImplementedError


class SquareGrid(BaseGraph):
    def __init__(self, width: int, height: int):
        super().__init__()
        self.width = width
        self.height = height
        self.walls: list[GridLocation] = []

    def in_bounds(self, id: GridLocation) -> bool:
        (x, y) = id
        return 0 <= x < self.width and 0 <= y < self.height

    def passable(self, id: GridLocation) -> bool:
        return id not in self.walls

    def neighbors(self, id: GridLocation) -> Iterator[GridLocation]:
        (x, y) = id
        neighbors = [(x + 1, y), (x - 1, y), (x, y - 1), (x, y + 1)]  # E W N S
        # see "Ugly paths" section for an explanation:
        if (x + y) % 2 == 0:
            neighbors.reverse()  # S N W E
        results = filter(self.in_bounds, neighbors)
        results = filter(self.passable, results)
        return results


class GridWithWeights(SquareGrid):
    def __init__(self, width: int, height: int):
        super().__init__(width, height)
        self.weights: dict[Tuple[GridLocation, GridLocation], float] = {}

    def get_edge_data(self, from_node: GridLocation, to_node: GridLocation) -> float:
        return self.weights.get((from_node, to_node), 0)
